package dp;

import org.junit.Test;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-01-09 20:52
 */
public class T46_translateNum {
    // 解题难点:
    // 怎么想到要用DP?
    //  首先,题目问种类数，要么是递归，要么是DP;
    //  在原先数字组合的基础上，加上一个数，种类数是不变的
    // 状态定义? 即dp[i]表示什么?
    // 怎么求递推关系? 这个是比较难想到的
    // 初始状态怎么求?


    @Test
    public void test() {
        translateNum(123);
    }

    // 法1:动态规划,从左到右
    //dp[i]表示 以s[i-1]为结尾的数字的翻译方案数量  比如dp[2]表示以s[1]结尾的数字翻译方案数量,也就是只有2个数，对应s[0] s[1]
    //k神那里可能会被误导，因为他里面的表示数据的xi是从1开始，而字符数组si是从0开始的,你会觉得dp[i]和s[i]对不上，你按照我的来理解就好了
    //Q:dp[0]为什么等于0?
    //A:当num的前两位组成的数字 ∈[10,25],显然有两种解法,dp[2]=dp[0]+dp[1]; dp[2]=2 dp[1]=1 ==> dp[0]=1
    // dp[0]只是在求递推式要用到，没有实际意义的
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int x=1; // <==> dp[0]
        int y=1; // <==> dp[1]
        int z;

        // 这里需要加等号,这样substring才能截取到最后一位; 还有循环的次数是 length-2+1 == length-1,
        // 因为每次都要截取2位数字,n位数字要截取n-1次(自己画一下就知道了)
        for (int i = 2; i <= s.length(); i++) {
            String ss = s.substring(i - 2, i);
            z = (ss.compareTo("10") >= 0 && ss.compareTo("25") <= 0) ? x + y : y;
            x = y;
            y = z;
        }
        return y;
    }


    // 法2: 和上面的做法是一致的，这里用了dp数组，所以空间复杂度为O(n)
    public int translateNum1(int num) {
        String s = String.valueOf(num);
        int dp[] = new int[s.length()+1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            String ss = s.substring(i - 2, i);
            if (ss.compareTo("10") >= 0 && ss.compareTo("25") <= 0) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[s.length()];
    }

    // 法3: 因为String s = String.valueOf(num) 需要消耗 O(n) 的空间,根据对称性,按照从右到左,可以使用求余来取个位数
    public int translateNum2(int num){
        int x = 1, y = 1, z;
        int ge = num % 10, shi; //个位ge 十位shi
        while (num > 0) { // 当 num/10=0,则shi=num%10取得的就是最高位的数字了，下次就应该结束循环了
            num /= 10;
            shi = num % 10; //更新十位数
            z = ((shi * 10 + ge) >= 10 && (shi * 10 + ge) <= 25) ? x + y : y;
            x = y;
            y = z;
            ge = shi; //更新个位数
        }
        return y;
    }
}